1. Field of the Invention
The present invention relates to a method of and apparatus for predictive coding for video frames.
2. Related Art
Predictive coding is a known technique for compressing video data. A video frame to be coded is compared with a reference frame and, rather than generating data indicative of the frame in isolation, data indicative of the differences between the reference frame and the frame to be coded are generated.
Comparing individual pixels between a reference frame and a frame to be coded becomes significantly less efficient if movement occurs within the image. However, given that movement often results in a re-arrangement of elements within an image, rather than a complete re-generation of an image, there is still a degree of inherent redundancy and advantage may be taken of this in order to facilitate further compression.
Movement within a video sequence often consists of an element being moved between different portions of an image. Given that video frames are presented at 25 or 30 per second, the degree of movement, for most observable objects, is relatively modest from one frame to another. Thus, as previously stated, movement often consists of the re-arrangement of pixel values and advantage may be taken of this inherent redundancy in order to facilitate further compression.
In theory, it would be possible to consider each individual pixel and, for each individual pixel, calculate a motion vector which, for a present frame under consideration, identifies the position of a pixel in a reference frame having a similar value. However, it will be appreciated that the generation of motion vectors for each individual pixel would provide little compression compared to transmitting the individual pixel values themselves, therefore, in order to achieve a degree of compression, it is necessary to calculate motion vectors for pixel regions and to assume that the whole region moves in a similar way. It is therefore known to divide video images into blocks of pixels consisting of, for example, squares made up of 16.times.16 pixels. Thus, before difference data is transmitted for each pixel within a block under consideration, a search is performed around a similar region in a reference frame to identify a block of pixels in the reference frame which, when compared with the block to be transmitted, results in, on average, the lowest absolute difference terms. Thus, once determined, these difference terms are transmitted, along with a motion vector identify the position of the identified block within the reference frame, relative to the position of the block under consideration.
Predictive coding can be used to generate difference values for the frame (n+1) which immediately follows the reference frame (n). In addition, the method may also be used to predict subsequent frames, such as frame n+2, n+3 etc. Under these circumstances the reference frame search area, for which movement has to be considered, increases for each incremental frame displacement. Furthermore, it should be appreciated that such an increase occurs in two dimensions.
In order to facilitate the calculation of motion vectors, it is possible to perform a telescoping technique, in which a motion vector is identified for the first frame displacement, between frame n and frame n+1 whereafter a motion vector is calculated for frame n+2 with reference to frame n using the motion vector calculated for frame n+1 to define a shifted detection range.
When coded frames are being transmitted in real time, it is desirable to transmit coded data as soon as possible. Thus, in the example given above, it is necessary to code frame n+1 in order that motion vectors may be calculated for frame n+2. Consequently, it is desirable, as soon as frame n+1 has been coded, to transmit this frame and thereafter to effect processing for the coding of frame n+2 so that this frame may be transmitted.
In some situations, particularly when transmitting data in accordance with an accepted standard, the desired order of transmission may differ from that which naturally results from the telescoping process. A problem therefore results in that it is difficult to implement a telescoping process if the resulting coded frames are generated in the wrong order.